package reviewAlgorithms.dynamicProgramming;

public class FindTargetSumWays {
    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        int S = 3;
        System.out.println(findTargetSumWays(nums,S));
        System.out.println(findTargetSumWays1(nums,S));
    }
    public static int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length < 1){
            return 0;
        }
        int numsSum = 0;
        for (int i = 0; i < nums.length; i++) {
            numsSum += nums[i];
        }

        if (S > numsSum){
            return 0;
        }
        int[][] dp = new int[nums.length][2*numsSum + 1];
        dp[0][nums[0] + numsSum] = 1;
        dp[0][-nums[0] + numsSum] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = -numsSum; j <= numsSum; j++) {
                if (j - nums[i] < -numsSum){
                    dp[i][j + numsSum] = dp[i - 1][j + numsSum + nums[i]];
                }else if (j + nums[i] > numsSum){
                    dp[i][j + numsSum] = dp[i - 1][j + numsSum - nums[i]];
                }else {
                    dp[i][j + numsSum] = dp[i - 1][j + numsSum - nums[i]] + dp[i - 1][j + numsSum + nums[i]];
                }
            }
        }
        return dp[nums.length - 1][numsSum + S];
    }

    public static int findTargetSumWays1(int[] nums, int S) {
        int sum = computeArraySum(nums);
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        int W = (sum + S) / 2;
        int[] dp = new int[W + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = W; i >= num; i--) {
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[W];
    }
    private static int computeArraySum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

}
